package com.mogujie.jessica.util;

import java.util.Collection;


/**
 * Methods for manipulating arrays.
 * 
 * @lucene.internal
 */

public final class ArrayUtil
{

    private ArrayUtil()
    {
    } // no instance

    /*
     * Begin Apache Harmony code
     * 
     * Revision taken on Friday, June 12.
     * https://svn.apache.org/repos/asf/harmony
     * /enhanced/classlib/archive/java6/modules
     * /luni/src/main/java/java/lang/Integer.java
     */

    /**
     * Parses the string argument as if it was an int value and returns the
     * result. Throws NumberFormatException if the string does not represent an
     * int quantity.
     * 
     * @param chars
     *            a string representation of an int quantity.
     * @return int the value represented by the argument
     * @throws NumberFormatException
     *             if the argument could not be parsed as an int quantity.
     */
    public static int parseInt(char[] chars) throws NumberFormatException
    {
        return parseInt(chars, 0, chars.length, 10);
    }

    /**
     * Parses a char array into an int.
     * 
     * @param chars
     *            the character array
     * @param offset
     *            The offset into the array
     * @param len
     *            The length
     * @return the int
     * @throws NumberFormatException
     *             if it can't parse
     */
    public static int parseInt(char[] chars, int offset, int len) throws NumberFormatException
    {
        return parseInt(chars, offset, len, 10);
    }

    /**
     * Parses the string argument as if it was an int value and returns the
     * result. Throws NumberFormatException if the string does not represent an
     * int quantity. The second argument specifies the radix to use when parsing
     * the value.
     * 
     * @param chars
     *            a string representation of an int quantity.
     * @param radix
     *            the base to use for conversion.
     * @return int the value represented by the argument
     * @throws NumberFormatException
     *             if the argument could not be parsed as an int quantity.
     */
    public static int parseInt(char[] chars, int offset, int len, int radix) throws NumberFormatException
    {
        if (chars == null || radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
        {
            throw new NumberFormatException();
        }
        int i = 0;
        if (len == 0)
        {
            throw new NumberFormatException("chars length is 0");
        }
        boolean negative = chars[offset + i] == '-';
        if (negative && ++i == len)
        {
            throw new NumberFormatException("can't convert to an int");
        }
        if (negative == true)
        {
            offset++;
            len--;
        }
        return parse(chars, offset, len, radix, negative);
    }

    private static int parse(char[] chars, int offset, int len, int radix, boolean negative) throws NumberFormatException
    {
        int max = Integer.MIN_VALUE / radix;
        int result = 0;
        for (int i = 0; i < len; i++)
        {
            int digit = Character.digit(chars[i + offset], radix);
            if (digit == -1)
            {
                throw new NumberFormatException("Unable to parse");
            }
            if (max > result)
            {
                throw new NumberFormatException("Unable to parse");
            }
            int next = result * radix - digit;
            if (next > result)
            {
                throw new NumberFormatException("Unable to parse");
            }
            result = next;
        }
        /*
         * while (offset < len) {
         * 
         * }
         */
        if (!negative)
        {
            result = -result;
            if (result < 0)
            {
                throw new NumberFormatException("Unable to parse");
            }
        }
        return result;
    }

    /*
     * 
     * END APACHE HARMONY CODE
     */

    /**
     * Returns an array size >= minTargetSize, generally over-allocating
     * exponentially to achieve amortized linear-time cost as the array grows.
     * 
     * NOTE: this was originally borrowed from Python 2.4.2 listobject.c sources
     * (attribution in LICENSE.txt), but has now been substantially changed
     * based on discussions from java-dev thread with subject "Dynamic array
     * reallocation algorithms", started on Jan 12 2010.
     * 
     * @param minTargetSize
     *            Minimum required value to be returned.
     * @param bytesPerElement
     *            Bytes used by each element of the array. See constants in
     *            {@link RamUsageEstimator}.
     * 
     * @lucene.internal
     */

    public static int oversize(int minTargetSize, int bytesPerElement)
    {

        if (minTargetSize < 0)
        {
            // catch usage that accidentally overflows int
            throw new IllegalArgumentException("invalid array size " + minTargetSize);
        }

        if (minTargetSize == 0)
        {
            // wait until at least one element is requested
            return 0;
        }

        // asymptotic exponential growth by 1/8th, favors
        // spending a bit more CPU to not tie up too much wasted
        // RAM:
        int extra = minTargetSize >> 3;

        if (extra < 3)
        {
            // for very small arrays, where constant overhead of
            // realloc is presumably relatively high, we grow
            // faster
            extra = 3;
        }

        int newSize = minTargetSize + extra;

        // add 7 to allow for worst case byte alignment addition below:
        if (newSize + 7 < 0)
        {
            // int overflowed -- return max allowed array size
            return Integer.MAX_VALUE;
        }

        if (Constants.JRE_IS_64BIT)
        {
            // round up to 8 byte alignment in 64bit env
            switch (bytesPerElement)
            {
            case 4:
                // round up to multiple of 2
                return (newSize + 1) & 0x7ffffffe;
            case 2:
                // round up to multiple of 4
                return (newSize + 3) & 0x7ffffffc;
            case 1:
                // round up to multiple of 8
                return (newSize + 7) & 0x7ffffff8;
            case 8:
                // no rounding
            default:
                // odd (invalid?) size
                return newSize;
            }
        } else
        {
            // round up to 4 byte alignment in 64bit env
            switch (bytesPerElement)
            {
            case 2:
                // round up to multiple of 2
                return (newSize + 1) & 0x7ffffffe;
            case 1:
                // round up to multiple of 4
                return (newSize + 3) & 0x7ffffffc;
            case 4:
            case 8:
                // no rounding
            default:
                // odd (invalid?) size
                return newSize;
            }
        }
    }

    public static int getShrinkSize(int currentSize, int targetSize, int bytesPerElement)
    {
        final int newSize = oversize(targetSize, bytesPerElement);
        // Only reallocate if we are "substantially" smaller.
        // This saves us from "running hot" (constantly making a
        // bit bigger then a bit smaller, over and over):
        if (newSize < currentSize / 2)
            return newSize;
        else
            return currentSize;
    }

    public static short[] grow(short[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            short[] newArray = new short[oversize(minSize, RamUsageEstimator.NUM_BYTES_SHORT)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static short[] grow(short[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static float[] grow(float[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            float[] newArray = new float[oversize(minSize, RamUsageEstimator.NUM_BYTES_FLOAT)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static float[] grow(float[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static double[] grow(double[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            double[] newArray = new double[oversize(minSize, RamUsageEstimator.NUM_BYTES_DOUBLE)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static double[] grow(double[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static short[] shrink(short[] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_SHORT);
        if (newSize != array.length)
        {
            short[] newArray = new short[newSize];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
            return array;
    }

    public static int[] grow(int[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            int[] newArray = new int[oversize(minSize, RamUsageEstimator.NUM_BYTES_INT)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static int[] grow(int[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static int[] shrink(int[] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_INT);
        if (newSize != array.length)
        {
            int[] newArray = new int[newSize];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
            return array;
    }

    public static long[] grow(long[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            long[] newArray = new long[oversize(minSize, RamUsageEstimator.NUM_BYTES_LONG)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static long[] grow(long[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static long[] shrink(long[] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_LONG);
        if (newSize != array.length)
        {
            long[] newArray = new long[newSize];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
            return array;
    }

    public static byte[] grow(byte[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            byte[] newArray = new byte[oversize(minSize, 1)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static byte[] grow(byte[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static byte[] shrink(byte[] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, 1);
        if (newSize != array.length)
        {
            byte[] newArray = new byte[newSize];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
            return array;
    }

    public static boolean[] grow(boolean[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            boolean[] newArray = new boolean[oversize(minSize, 1)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static boolean[] grow(boolean[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static boolean[] shrink(boolean[] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, 1);
        if (newSize != array.length)
        {
            boolean[] newArray = new boolean[newSize];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
            return array;
    }

    public static char[] grow(char[] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            char[] newArray = new char[oversize(minSize, RamUsageEstimator.NUM_BYTES_CHAR)];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
            return array;
    }

    public static char[] grow(char[] array)
    {
        return grow(array, 1 + array.length);
    }

    public static char[] shrink(char[] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_CHAR);
        if (newSize != array.length)
        {
            char[] newArray = new char[newSize];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
            return array;
    }

    public static int[][] grow(int[][] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            int[][] newArray = new int[oversize(minSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF)][];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
        {
            return array;
        }
    }

    public static int[][] grow(int[][] array)
    {
        return grow(array, 1 + array.length);
    }

    public static int[][] shrink(int[][] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF);
        if (newSize != array.length)
        {
            int[][] newArray = new int[newSize][];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
        {
            return array;
        }
    }

    public static float[][] grow(float[][] array, int minSize)
    {
        assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
        if (array.length < minSize)
        {
            float[][] newArray = new float[oversize(minSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF)][];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        } else
        {
            return array;
        }
    }

    public static float[][] grow(float[][] array)
    {
        return grow(array, 1 + array.length);
    }

    public static float[][] shrink(float[][] array, int targetSize)
    {
        assert targetSize >= 0 : "size must be positive (got " + targetSize + "): likely integer overflow?";
        final int newSize = getShrinkSize(array.length, targetSize, RamUsageEstimator.NUM_BYTES_OBJECT_REF);
        if (newSize != array.length)
        {
            float[][] newArray = new float[newSize][];
            System.arraycopy(array, 0, newArray, 0, newSize);
            return newArray;
        } else
        {
            return array;
        }
    }

    /**
     * Returns hash of chars in range start (inclusive) to end (inclusive)
     */
    public static int hashCode(char[] array, int start, int end)
    {
        int code = 0;
        for (int i = end - 1; i >= start; i--)
            code = code * 31 + array[i];
        return code;
    }

    /**
     * Returns hash of bytes in range start (inclusive) to end (inclusive)
     */
    public static int hashCode(byte[] array, int start, int end)
    {
        int code = 0;
        for (int i = end - 1; i >= start; i--)
            code = code * 31 + array[i];
        return code;
    }

    // Since Arrays.equals doesn't implement offsets for equals
    /**
     * See if two array slices are the same.
     * 
     * @param left
     *            The left array to compare
     * @param offsetLeft
     *            The offset into the array. Must be positive
     * @param right
     *            The right array to compare
     * @param offsetRight
     *            the offset into the right array. Must be positive
     * @param length
     *            The length of the section of the array to compare
     * @return true if the two arrays, starting at their respective offsets, are
     *         equal
     * 
     * @see java.util.Arrays#equals(char[], char[])
     */
    public static boolean equals(char[] left, int offsetLeft, char[] right, int offsetRight, int length)
    {
        if ((offsetLeft + length <= left.length) && (offsetRight + length <= right.length))
        {
            for (int i = 0; i < length; i++)
            {
                if (left[offsetLeft + i] != right[offsetRight + i])
                {
                    return false;
                }

            }
            return true;
        }
        return false;
    }

    /*
     * DISABLE THIS FOR NOW: This has performance problems until Java creates
     * intrinsics for Class#getComponentType() and Array.newInstance() public
     * static <T> T[] grow(T[] array, int minSize) { assert minSize >= 0:
     * "size must be positive (got " + minSize + "): likely integer overflow?";
     * if (array.length < minSize) {
     * 
     * @SuppressWarnings("unchecked") final T[] newArray = (T[])
     * Array.newInstance(array.getClass().getComponentType(), oversize(minSize,
     * RamUsageEstimator.NUM_BYTES_OBJECT_REF)); System.arraycopy(array, 0,
     * newArray, 0, array.length); return newArray; } else return array; }
     * 
     * public static <T> T[] grow(T[] array) { return grow(array, 1 +
     * array.length); }
     * 
     * public static <T> T[] shrink(T[] array, int targetSize) { assert
     * targetSize >= 0: "size must be positive (got " + targetSize +
     * "): likely integer overflow?"; final int newSize =
     * getShrinkSize(array.length, targetSize,
     * RamUsageEstimator.NUM_BYTES_OBJECT_REF); if (newSize != array.length) {
     * 
     * @SuppressWarnings("unchecked") final T[] newArray = (T[])
     * Array.newInstance(array.getClass().getComponentType(), newSize);
     * System.arraycopy(array, 0, newArray, 0, newSize); return newArray; } else
     * return array; }
     */

    // Since Arrays.equals doesn't implement offsets for equals
    /**
     * See if two array slices are the same.
     * 
     * @param left
     *            The left array to compare
     * @param offsetLeft
     *            The offset into the array. Must be positive
     * @param right
     *            The right array to compare
     * @param offsetRight
     *            the offset into the right array. Must be positive
     * @param length
     *            The length of the section of the array to compare
     * @return true if the two arrays, starting at their respective offsets, are
     *         equal
     * 
     * @see java.util.Arrays#equals(char[], char[])
     */
    public static boolean equals(int[] left, int offsetLeft, int[] right, int offsetRight, int length)
    {
        if ((offsetLeft + length <= left.length) && (offsetRight + length <= right.length))
        {
            for (int i = 0; i < length; i++)
            {
                if (left[offsetLeft + i] != right[offsetRight + i])
                {
                    return false;
                }

            }
            return true;
        }
        return false;
    }

    public static int[] toIntArray(Collection<Integer> ints)
    {

        final int[] result = new int[ints.size()];
        int upto = 0;
        for (int v : ints)
        {
            result[upto++] = v;
        }

        // paranoia:
        assert upto == result.length;

        return result;
    }

}